/*
 * QuickSort.cpp
 *
 *  Created on: 2011-2-23
 *      Author:蓝达斌
 *
 *   Copyright   : Copyright © 2011 Binda&Aeolus
                   All Rights Reserved
 */
#include "QuickSort.h"

/**
 * 升序排列
 */
template <class Type>
    void  QuickSort::Sort_Ascend(vector<Type> &data,int start,int end)
    {
      if(start<end)
      {
    	  int q=Partion_Asc(data,start,end);
    	  Sort_Ascend(data,start,q-1);
    	  Sort_Ascend(data,q+1,end);
      }

    }




template <class Type>
	int QuickSort::Partion_Asc(vector<Type> &data,int start,int end)
	{
    int i=start,j=end+1;
    Type x=data[start];
    while(true)
    {
    	while(data[++i]<x&&i<end);
    	while(data[--j]>x);
    	if(i>=j) break;
    	Utility::swap(data[i],data[j]);

    }

    data[start]=data[j];
    data[j]=x;
    return j;

	}

/**
 * 降序排列
 */

template <class Type>
    void  QuickSort::Sort_Descend(vector<Type> &data,int start,int end)
    {
      if(start<end)
      {
    	  int q=Partion_Desc(data,start,end);
    	  Sort_Descend(data,start,q-1);
    	  Sort_Descend(data,q+1,end);
      }

    }


template <class Type>
	int QuickSort::Partion_Desc(vector<Type> &data,int start,int end)
	{
    int i=start,j=end+1;
    Type x=data[start];
    while(true)
    {
    	while(data[++i]>x&&i<end);
    	while(data[--j]<x);
    	if(i>=j) break;
    	Utility::swap(data[i],data[j]);

    }

    data[start]=data[j];
    data[j]=x;
    return j;

	}

